package com.company.class10;

import java.util.Arrays;

/**
 * @Classname QuickSort
 * @Description 类型说明
 * @Date 2022/5/2 21:50
 * @Created by zbw
 */

public class QuickSort {
    public static void main(String[] args) {
        int a[] = {4,2,9,1,3,8,5};
        //起止位置声明
        int start = 0;
        int end = a.length -1;
//        //定义基准值，并声明左右下标
//        int left = start;
//        int rigth = end;
//        int base = a[0];
//
//        while(left < rigth){
//            //从右往左的遍历
//            while (left < rigth){
//                //如果right值比基准值大，不用动，right--
//                if(a[rigth] > base){
//                    rigth--;
//                }else {
//                    //如果比基准值小，交换基准值left和right的位置，切换到从左往右进行遍历，left++
//                    a[left] = a[rigth];
//                    a[rigth] = base;
//                    left++;
//                    break;
//                }
//
//            }
//
//            while (left < rigth){
//                //从左往右的遍历
//                if(a[left] < base){
//                    left++;
//                }else {
//                    //如果比基准值大，交换 left和right（基准值）的位置，切换到从右往左进行遍历，rigth--
//                    a[rigth] = a[left];
//                    a[left] = base;
//                    rigth--;
//                    break;
//                }
//
//            }
//        }
//        System.out.println(Arrays.toString(a));

        quickSort(a,start,end);
        System.out.println(Arrays.toString(a));

    }

    public static void quickSort(int[] a,int start,int end){
        int base = a[start];
        int left =start;
        int right = end;

        while(left < right){
            //从右往左的遍历
            while (left < right){
                //如果right值比基准值大，不用动，right--
                if(a[right] > base){
                    right--;
                }else {
                    //如果比基准值小，交换基准值left和right的位置，切换到从左往右进行遍历，left++
                    a[left] = a[right];
                    a[right] = base;
                    left++;
                    break;
                }

            }

            while (left < right){
                //从左往右的遍历
                if(a[left] < base){
                    left++;
                }else {
                    //如果比基准值大，交换 left和right（基准值）的位置，切换到从右往左进行遍历，rigth--
                    a[right] = a[left];
                    a[left] = base;
                    right--;
                    break;
                }

            }

        }

        //排完之后，判断是否接着排序：

        //左边的条件：left - start <= 1
        //不在递归，就是不调用这个方法了。
        if(left - start > 1){

            quickSort(a,start,left-1);
        }

        //右边的条件：end - left <= 1
        if(end - left > 1){
            quickSort(a,left+1,end);
        }

    }



}
